package com.leecode.xiehf.page_01;

public class Solution_0044 {

    public static void main(String[] args) {
        Solution_0044 solution = new Solution_0044();
        boolean abc = solution.isMatch("adceb", "*a*b");
        System.out.println(abc);
    }


    /**
     * 动态规划
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        if (m == 0 && n == 0) {
            return true;
        }
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                // 上一个如果为true
                if (dp[0][j - 1]) {
                    dp[0][j] = true;
                    for (int i = 1; i <= m; i++) {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char ss = s.charAt(i - 1);
                char pp = p.charAt(j - 1);
                if (ss == pp || pp == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pp == '*') {
                    if (dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j]) {
                        dp[i][j] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }

    // todo 看不懂的
    public boolean isMatch1(String s, String p) {
        int sn = s.length();
        int pn = p.length();
        int i = 0;
        int j = 0;
        int start = -1;
        int match = 0;
        while (i < sn) {
            if (j < pn && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                i++;
                j++;
            } else if (j < pn && p.charAt(j) == '*') {
                start = j;
                match = i;
                j++;
            } else if (start != -1) {
                j = start + 1;
                match++;
                i = match;
            } else {
                return false;
            }
        }
        while (j < pn) {
            if (p.charAt(j) != '*') {
                return false;
            }
            j++;
        }
        return true;
    }
}
